<?php
class BinarySearchTree implements Countable,IteratorAggregate
{
    /**
     * @var BinaryNode $root 根节点
     */
    public $root=null;
    
    public $count=0;
    public function count()
    {
        return $this->count;
    }

    /**
     * 查找与指定的值相同的节点
     * @param mix $item 要查找的值
     * @param BinaryNode $node 起始节点
     * @param bool $is_create 如果节点为空，是否创建并返回新建的节点
     * @return BinaryNode|false
     */
    public function find($item,$node=null,$is_create=false)
    {
        if($node === null){
            if($this->root === null){
                if($is_create){
                    $this->root=BinaryNode::create($item);
                    return $this->root;
                }
                else{
                    return false;
                }
            }
            else{
                return $this->find($item,$this->root);
            }
        }
        elseif($node->data === $item){
            return $node;
        }
        elseif($node->data > $item){
            if($node->left === null){
                if($is_create){
                    $this->left=BinaryNode::create($item);
                    return $this->left;
                }
                else{
                    return false;
                }
            }
            else{
                return $this->find($item,$node->left);
            }
        }
        else{
            if($node->right === null){
                if($is_create){
                    $this->right=BinaryNode::create($item);
                    return $this->right;
                }
                else{
                    return false;
                }
            }
            else{
                return $this->find($item,$node->right);
            }
        }
    }
    /**
     * @param BinaryNode $node 要查找的起始节点
     * @return bool
     */
    public function contains($item,$node=null)
    {
        if($node === null){
            if($this->root === null){
                return false;
            }
            else{
                return $this->contains($item,$this->root);
            }
        }
        elseif($node->data === $item){
            return true;
        }
        elseif($node->data > $item){
            if($node->left === null){
                return false;
            }
            else{
                return $this->contains($item,$node->left);
            }
        }
        else{
            if($node->right === null){
                return false;
            }
            else{
                return $this->contains($item,$node->right);
            }
        }
    }
    /**
     * 插入一个数组
     * @return void
     */
    public function insertList($list)
    {
        foreach($list as $item){
            $this->insert($item);
        }
    }
    /**
     * 插入多个新数据
     * @return void
     */
    public function insertMulti(...$items)
    {
        foreach($items as $item){
            $this->insert($item);
        }
    }
    /**
     * 插入一个新数据
     * @param mixed $item
     * @return void
     */
    public function insert($item)
    {
        $node=BinaryNode::create($item);
        if($this->root === null){
            $this->root=$node;
        }
        else{
            $this->insertTo($node,$this->root);
        }
        $this->count++;
    }
    /**
     * 将一个节点插入到一个子树下
     * @param BinaryNode $node
     * @param BinaryNode $sup
     */
    protected function insertTo($node,$sup)
    {
        if($sup->data > $node->data){
            if($sup->left === null){
                $sup->left=$node;
            }
            else{
                $this->insertTo($node,$sup->left);
            }
        }
        else{
            if($sup->right === null){
                $sup->right=$node;
            }
            else{
                $this->insertTo($node,$sup->right);
            }
        }
    }
    /**
     * @param BinaryNode $node 要查找的起始节点
     * @return true
     */
    public function remove($item,$node=null)
    {
        if($node === null){
            if($this->root === null){
                return false;
            }
            else{
                return $this->remove($item,$this->root);
            }
        }
        elseif($node->data === $item){
            $this->root=null;
            $this->count--;
            return true;
        }
        elseif($node->data > $item){
            if($node->left === null){
                return false;
            }
            else{
                return $this->remove($item,$node->left);
            }
        }
        else{
            if($node->right === null){
                return false;
            }
            else{
                return $this->remove($item,$node->right);
            }
        }
    }
    public function findMin()
    {

    }
    public function findMax()
    {

    }
    /**
     * 获取迭代器
     */
    public function getIterator()
    {
        return new MinToMixIterator($this);
    }
    public function __toString()
    {
        $output=new BinaryTreeOutput();
        return $output->fetch($this->root);
    }
}



